We study online scheduling problems on a single processor that can be viewedas extensions of the well-studied problem of minimizing total weighted flowtime. In particular, we provide a framework of analysis that is derived byduality properties, does not rely on potential functions and is applicable to avariety of scheduling problems. A key ingredient in our approach is bypassingthe need for "black-box" rounding of fractional solutions, which yieldsimproved competitive ratios. We begin with an interpretation of Highest-Density-First (HDF) as aprimal-dual algorithm, and a corresponding proof that HDF is optimal for totalfractional weighted flow time (and thus scalable for the integral objective).Building upon the salient ideas of the proof, we show how to apply and extendthis analysis to the more general problem of minimizing $\sum_j w_j g(F_j)$,where $w_j$ is the job weight, $F_j$ is the flow time and $g$ is anon-decreasing cost function. Among other results, we present improvedcompetitive ratios for the setting in which $g$ is a concave function, and thesetting of same-density jobs but general cost functions. We further apply ourframework of analysis to online weighted completion time with general costfunctions as well as scheduling under polyhedral constraints.
展开▼
机译：我们在单个处理器上研究在线调度问题，该问题可以看作是经过研究的，将总加权流时间最小化的扩展。特别是，我们提供了一种通过二重性属性得出的分析框架，该框架不依赖于潜在功能，并且适用于各种调度问题。我们方法中的一个关键因素是绕过对分数解决方案进行“黑箱”四舍五入的需求，这可以提高竞争比率。我们首先将最高密度优先（HDF）解释为原始对偶算法，并相应证明证明HDF对于总分数加权流动时间是最佳的（因此对于积分目标是可扩展的）。证明，我们将展示如何将这种分析方法应用和扩展到使$ \ sum_j w_j g（F_j）$最小化的更普遍的问题，其中$ w_j $是工作权重，$ F_j $是流水时间，$ g $是匿名-降低成本函数。在其他结果中，我们给出了其中$ g $是凹函数的设置和相同密度的工作但具有一般成本函数的设置的改进的竞争比率。我们进一步将分析框架应用于具有一般成本函数的在线加权完成时间，以及在多面体约束下进行调度。
展开▼
